মাক্স-হিপ এবং মিন-হিপের ধারণা
হিপ (Heap) হলো একটি বিশেষ ধরনের বাইনারি ট্রি, যা একটি সম্পূর্ণ বাইনারি ট্রি আকারে সাজানো থাকে। হিপের দুটি প্রধান প্রকারভেদ রয়েছে: মাক্স-হিপ (Max-Heap) এবং মিন-হিপ (Min-Heap)। এই ডেটা স্ট্রাকচারটি সাধারণত প্রায়োরিটি কিউ, ডেটা প্রসেসিং এবং দ্রুততম উপাদান খুঁজে বের করার জন্য ব্যবহৃত হয়।
১. মাক্স-হিপ (Max-Heap)
মাক্স-হিপ এমন একটি হিপ যেখানে প্রতিটি প্যারেন্ট নোড তার সমস্ত চাইল্ড নোডগুলির চেয়ে বড় বা সমান মান ধারণ করে। মাক্স-হিপের মূল নোড বা রুট সর্বোচ্চ মান ধারণ করে।
বৈশিষ্ট্য:
- প্রতিটি প্যারেন্ট নোডের মান তার চাইল্ড নোডগুলোর মানের চেয়ে বড় বা সমান হবে।
- রুট নোডে সর্বাধিক মান থাকে।
উদাহরণ:
একটি মাক্স-হিপের উদাহরণ নিচে দেওয়া হলো:
50
/ \
30 40
/ \ / \
10 15 20 35
এখানে, 50 হলো রুট এবং এটি সর্বাধিক মান, এবং প্রতিটি প্যারেন্ট নোড তার চাইল্ড নোডের চেয়ে বড়।
মাক্স-হিপের ব্যবহার:
- প্রায়োরিটি কিউ: মাক্স-হিপ ব্যবহার করে সর্বোচ্চ প্রায়োরিটি আইটেম দ্রুত খুঁজে বের করা যায়।
- সাজানো ডেটা খুঁজে বের করা: হিপ সর্টিংয়ের জন্য মাক্স-হিপ ব্যবহার করা হয়।
২. মিন-হিপ (Min-Heap)
মিন-হিপ এমন একটি হিপ যেখানে প্রতিটি প্যারেন্ট নোড তার সমস্ত চাইল্ড নোডগুলির চেয়ে ছোট বা সমান মান ধারণ করে। মিন-হিপের মূল নোড বা রুট সর্বনিম্ন মান ধারণ করে।
বৈশিষ্ট্য:
- প্রতিটি প্যারেন্ট নোডের মান তার চাইল্ড নোডগুলোর মানের চেয়ে ছোট বা সমান হবে।
- রুট নোডে সর্বনিম্ন মান থাকে।
উদাহরণ:
একটি মিন-হিপের উদাহরণ নিচে দেওয়া হলো:
10
/ \
15 20
/ \ / \
30 40 35 50
এখানে, 10 হলো রুট এবং এটি সর্বনিম্ন মান, এবং প্রতিটি প্যারেন্ট নোড তার চাইল্ড নোডের চেয়ে ছোট।
মিন-হিপের ব্যবহার:
- প্রায়োরিটি কিউ: মিন-হিপ ব্যবহার করে সর্বনিম্ন প্রায়োরিটি আইটেম দ্রুত খুঁজে বের করা যায়।
- ডেটা প্রসেসিং: ডেটার মধ্যে সবচেয়ে ছোট মান দ্রুত খুঁজে বের করতে মিন-হিপ ব্যবহার করা হয়।
মাক্স-হিপ এবং মিন-হিপের তুলনামূলক চার্ট
| বৈশিষ্ট্য | মাক্স-হিপ (Max-Heap) | মিন-হিপ (Min-Heap) |
|---|---|---|
| রুট নোডের মান | সর্বোচ্চ মান | সর্বনিম্ন মান |
| প্রায়োরিটি কিউ | সর্বোচ্চ প্রায়োরিটির আইটেম খুঁজে বের করা | সর্বনিম্ন প্রায়োরিটির আইটেম খুঁজে বের করা |
| প্রযুক্তিগত ব্যবহার | হিপ সর্টে ডেসেন্ডিং অর্ডারে সাজানোর জন্য | হিপ সর্টে আসেন্ডিং অর্ডারে সাজানোর জন্য |
উদাহরণ: মাক্স-হিপ এবং মিন-হিপ (Python কোড)
Python-এ মিন-হিপ তৈরি করতে heapq মডিউল ব্যবহার করা যায়। তবে, মাক্স-হিপের জন্য heapq কে উল্টো মান ব্যবহার করে মিন-হিপের মতো করে কাজ করানো যায়।
import heapq
# মিন-হিপ উদাহরণ
min_heap = []
heapq.heappush(min_heap, 10)
heapq.heappush(min_heap, 15)
heapq.heappush(min_heap, 5)
print("Min-Heap:", min_heap) # আউটপুট: Min-Heap: [5, 15, 10]
# মাক্স-হিপ উদাহরণ
max_heap = []
heapq.heappush(max_heap, -10) # মানটি নেগেটিভ করে ইনসার্ট করা হয়
heapq.heappush(max_heap, -15)
heapq.heappush(max_heap, -5)
print("Max-Heap:", [-x for x in max_heap]) # আউটপুট: Max-Heap: [15, 10, 5]
উপসংহার
মাক্স-হিপ এবং মিন-হিপ ডেটা স্ট্রাকচারগুলো বিশেষত প্রায়োরিটি কিউ এবং হিপ সর্টে ব্যবহৃত হয়। মাক্স-হিপ সর্বোচ্চ মান খুঁজে বের করতে এবং মিন-হিপ সর্বনিম্ন মান খুঁজে বের করতে কার্যকর।
Read more
